package algorithm.difficult;

import java.util.Arrays;

public class DieSimulator1223 {

    /***
     * https://leetcode.cn/problems/dice-roll-simulation/description/
     * @param n
     * @param rollMax
     * @return
     */
    public int dieSimulator2(int n, int[] rollMax) {
        int count = 0;
        for (int i = 0; i < rollMax.length; i++) {
            int[] arr = Arrays.copyOf(rollMax, 6);
            arr[i]--;
            count += recursion(n - 1, arr, i, 1);
        }
        return count;
    }

    public int recursion(int n, int[] rollMax, int addIndex, int addNum) {
        if (n == 1) {
            int count = 0;
            for (int max : rollMax) {
                if (max > 0) {
                    count++;
                }
            }
            return count;
        }
        int res = 0;
        for (int i = 0; i < rollMax.length; i++) {
            if (rollMax[i] == 0) {
                continue;
            }
            int[] arr = Arrays.copyOf(rollMax, 6);
            arr[i]--;
            if (addIndex != i) {
                arr[addIndex] += addNum;
                addNum = 1;
            } else {
                addNum++;
            }
            res += recursion(n - 1, arr, i, addNum);
        }
        return res;
    }

    public static void main(String[] args) {
//        System.out.println(new DieSimulator1223().dieSimulator(4, new int[]{0, 1, 2, 2, 2, 3}));
//        System.out.println(new DieSimulator1223().dieSimulator(4, new int[]{1, 0, 2, 2, 2, 3}));
//        System.out.println(new DieSimulator1223().dieSimulator(4, new int[]{1, 1, 1, 2, 2, 3}));
//        System.out.println(new DieSimulator1223().dieSimulator(4, new int[]{1, 1, 2, 1, 2, 3}));
//        System.out.println(new DieSimulator1223().dieSimulator(4, new int[]{1, 1, 2, 2, 1, 3}));
//        System.out.println(new DieSimulator1223().dieSimulator(4, new int[]{1, 1, 2, 2, 2, 2}));
        System.out.println("----------------------------------------------------------------");
        System.out.println(new DieSimulator1223().dieSimulator(3, new int[]{1, 1, 1, 2, 2, 3}));

    }

    /**
     * dp[i][j][k] 代表着第i次投掷，数字j连续出现k次的合法序列数。
     * 最后结果为dp[n][0~5][1~k]的累加
     * <p>
     * 以上次i-1 和本次i 为例。转移方程：
     * 如果本次投掷点数p与上次j不同  dp[i][p][1] +=  dp[i-1][0～5排除本次投掷点数][k]
     * 如果本次投掷点数p与上次j相同 且 该点数还没超过限定最长连续数字  dp[i][p][k+1] += dp[i-1][j][k]
     */
    static final int MOD = 1000000007;

    public int dieSimulator(int n, int[] rollMax) {
        //dp数组
        int[][][] dp = new int[n + 1][6][16];
        //初始化 dp[1][0~5][1] = 1
        for (int j = 0; j < 6; j++) {
            dp[1][j][1] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 6; j++) {
                for (int k = 1; k <= rollMax[j]; k++ ) {
                    for (int p = 0; p < 6; p++) {
                        if (j == p) {
                            if (k + 1 <= rollMax[j]) {
                                dp[i][p][k + 1] = (dp[i][p][k + 1] + dp[i - 1][j][k]) % MOD;
                            }
                        }else {
                            dp[i][p][1] = (dp[i][p][1] + dp[i - 1][j][k]) % MOD;
                        }
                    }
                }
            }
        }
        //计算合法数量
        int res = 0;
        for (int i = 0; i < 6; i++) {
            for (int j = 1; j <= rollMax[i]; j++) {
                res = (res + dp[n][i][j]) % MOD;
            }
        }
        return res;
    }


}
